The probabilistic serial (PS) rule is one of the most prominent randomizedrules for the assignment problem. It is well-known for its superior fairnessand welfare properties. However, PS is not immune to manipulative behaviour bythe agents. We examine computational and non-computational aspects ofstrategising under the PS rule. Firstly, we study the computational complexityof an agent manipulating the PS rule. We present polynomial-time algorithms foroptimal manipulation. Secondly, we show that expected utility best responsescan cycle. Thirdly, we examine the existence and computation of Nashequilibrium profiles under the PS rule. We show that a pure Nash equilibrium isguaranteed to exist under the PS rule. For two agents, we identify twodifferent types of preference profiles that are not only in Nash equilibriumbut can also be computed in linear time. Finally, we conduct experiments tocheck the frequency of manipulability of the PS rule under differentcombinations of the number of agents, objects, and utility functions.
展开▼
